class Solution
{
public:
    // dijkstra, 但图中边数太多， 可达到 O((mn)^2)， 会超时
    int minimumVisitedCells(vector<vector<int>> &grid)
    {
        int m = grid.size();
        int n = grid[0].size();
        vector<int> rowMostReach(m, -1);
        vector<int> colMostReach(n, -1);

        queue<array<int, 2>> q;
        q.push({0, 0});
        rowMostReach[0] = colMostReach[0] = 0;
        int step = 0;
        while (!q.empty())
        {
            ++step;
            int qSize = q.size();
            for (int _ = 0; _ < qSize; ++_)
            {
                auto [row, col] = q.front();
                if (row == m - 1 && col == n - 1)
                {
                    return step;
                }
                q.pop();

                for (int nextCol = rowMostReach[row] + 1; nextCol <= min(n - 1, col + grid[row][col]); ++nextCol)
                {
                    q.push({row, nextCol});
                    rowMostReach[row] = nextCol;
                }

                for (int nextRow = colMostReach[col] + 1; nextRow <= min(m - 1, row + grid[row][col]); ++nextRow)
                {
                    q.push({nextRow, col});
                    colMostReach[col] = nextRow;
                }
            }
        }
        return -1;
    }
    // BFS, 答案不对, 但不知道为啥, 可能是不能这么剪枝
    int minimumVisitedCells(vector<vector<int>> &grid)
    {
        int m = grid.size();
        int n = grid[0].size();

        vector<vector<int>> minSteps(m, vector<int>(n, INT_MAX));
        minSteps[0][0] = 0;

        auto compareDistance = [](auto &a1, auto &a2)
        {
            return a1[2] > a2[2];
        };
        priority_queue<array<int, 3>, vector<array<int, 3>>, decltype(compareDistance)> q(compareDistance);
        q.push({0, 0, 0});

        while (!q.empty())
        {
            auto [row, col, step] = q.top();
            if (row == m - 1 && col == n - 1)
            {
                return step;
            }
            q.pop();

            if (step > minSteps[row][col])
            {
                continue;
            }

            for (int nextCol = col + 1; nextCol <= min(n - 1, col + grid[row][col]); ++nextCol)
            {
                if (minSteps[row][nextCol] > step + 1)
                {
                    minSteps[row][nextCol] = step + 1;
                    q.push({row, nextCol, step + 1});
                }
            }

            for (int nextRow = row + 1; nextRow <= min(m - 1, row + grid[row][col]); ++nextRow)
            {
                if (minSteps[nextRow][col] > step + 1)
                {
                    minSteps[nextRow][col] = step + 1;
                    q.push({nextRow, col, step + 1});
                }
            }
        }
        return -1;
    }
};